
public class Text {

    public static void main(String[] args) {

        MySingleList mySingleList1 = new MySingleList();

        mySingleList1.addLast(1);
        mySingleList1.addLast(2);
        mySingleList1.addLast(3);
        mySingleList1.addLast(4);
        mySingleList1.addLast(5);

        MySingleList.ListNode head = mySingleList1.head;


        MySingleList.ListNode cmp = head.next;

        head.next = null;

        while (cmp != null){
            MySingleList.ListNode tmp = cmp.next;
            cmp.next = head;
            head = cmp;
            cmp = tmp;
        }

        System.out.println(head.val);

    }

    //给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null

    public MySingleList.ListNode detectCycle(MySingleList.ListNode head) {
        if(head == null){
            return null;
        }

        MySingleList.ListNode slow = head;
        MySingleList.ListNode fast = head;
        MySingleList.ListNode tmp = head;

        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;

            if(fast == slow){
                while (tmp != slow){
                    tmp = tmp.next;
                    slow = slow.next;
                }
                return tmp;
            }
        }
        return null;
    }

    //合并两个有序链表
    public MySingleList.ListNode mergeTwoLists(MySingleList.ListNode list1,
                                               MySingleList.ListNode list2) {

        MySingleList.ListNode head = new MySingleList.ListNode(-1);
        MySingleList.ListNode tmp = head;

        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                tmp.next = list1;
                list1 = list1.next;
            }else{
                tmp.next = list2;
                list2 = list2.next;
            }
            tmp = tmp.next;
        }
        if(list1 == null){
            tmp.next = list2;
        }
        if(list2 == null){
            tmp.next = list1;
        }

        return head.next;

        /*MySingleList.ListNode cur1 = list1;
        MySingleList.ListNode cur2 = list2;

        MySingleList.ListNode tmp = null;

        while(cur1 != null && cur2 != null){
            if(cur1.val < cur2.val){
                tmp = cur1;
                cur1 = cur1.next;
            }else{
                tmp = cur2;
                cur2 = cur2.next;
            }
        }
        if(cur1 == null){
            tmp.next = cur2;
        }
        if(cur2 == null){
            tmp.next = cur1;
        }

        return tmp;*/
    }

    //给你一个链表的头节点 head ，判断链表中是否有环。
    public static boolean hasCycle(MySingleList.ListNode head) {

        if(head == null){
            return false;
        }

        MySingleList.ListNode slow = head;
        MySingleList.ListNode fast = head;

        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;

            if(fast == slow){
                return true;
            }
        }
        return false;
    }



    /*public static boolean hasCycle(MySingleList.ListNode head) {

        if(head == null || head.next == null){
            return false;
        }

        MySingleList.ListNode slow = head;
        MySingleList.ListNode fast = head.next;

        while (fast != slow){
            if(fast == null || fast.next == null){
                return false;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }*/

    public static void main4(String[] args) {
        MySingleList mySingleList1 = new MySingleList();

        mySingleList1.addLast(1);
        mySingleList1.addLast(2);

        System.out.println(hasCycle(mySingleList1.head));
    }


    //给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
    public static MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA,
                                                            MySingleList.ListNode headB) {
        int len1 = 0;
        int len2 = 0;
        MySingleList.ListNode node1 = headA;
        MySingleList.ListNode node2 = headB;

        while(node1 != null){
            len1 ++;
            node1 = node1.next;
        }

        while(node2 != null){
            len2 ++;
            node2 = node2.next;
        }

        node1 = headA;
        node2 = headB;

        int defference = len1 -len2;
        if(defference < 0){
            node1 = headB;
            node2 = headA;
            defference = len2 -len1;
        }

        while (defference != 0){
            node1 = node1.next;
            defference--;
        }
        while (node1 != node2){
            node1 = node1.next;
            node2 = node2.next;
        }

        if(node1 == null){
            return null;
        }
        return node1;
    }

    public static void ChangeList(MySingleList.ListNode headA,
                                  MySingleList.ListNode headB){
        headA.next.next.next = headB.next.next;
    }

    public static void main3(String[] args) {

        MySingleList mySingleList1 = new MySingleList();

        mySingleList1.addLast(12);
        mySingleList1.addLast(34);
        mySingleList1.addLast(10);
        mySingleList1.addLast(54);
        mySingleList1.addLast(5);

        MySingleList mySingleList2 = new MySingleList();

        mySingleList2.addLast(29);
        mySingleList2.addLast(30);
        mySingleList2.addLast(39);
        mySingleList2.addLast(17);
        mySingleList2.addLast(9);

        ChangeList(mySingleList1.head,mySingleList2.head);

        MySingleList.ListNode cur = getIntersectionNode(mySingleList1.head,mySingleList2.head);

        System.out.println(cur.val);

    }

    //链表的回文结构

    public static boolean chkPalindrome(MySingleList.ListNode head) {
        // write code here
        MySingleList.ListNode fast = head;
        MySingleList.ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }

        MySingleList.ListNode cur = slow.next;
        while (cur != null){
            MySingleList.ListNode curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;
        }

        MySingleList.ListNode tmp = head;
        while (tmp != slow){
            if(tmp.val != slow.val){
                return false;
            }
            if(tmp.next.val == slow.val){
                return true;
            }
            tmp = tmp.next;
            slow = slow.next;
        }
        return true;
    }


    //现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
    public static MySingleList.ListNode partition(MySingleList.ListNode head, int x) {

        MySingleList.ListNode cur = head;
        MySingleList.ListNode sh = null;
        MySingleList.ListNode sl = null;
        MySingleList.ListNode bh = null;
        MySingleList.ListNode bl = null;

        while(cur != null){
            if(cur.val < x){
                if(sh == null){
                    sh = sl = cur;
                }else{
                    sl.next = cur;
                    sl = sl.next;
                }
            }else{
                if(bh == null){
                    bh = bl = cur;
                }else{
                    bl.next = cur;
                    bl = bl.next;
                }
            }
            cur = cur.next;
        }
        if(sh == null){
            return bh;
        }
        sl.next = bh;
        if (bh != null) {
            bl.next = null;
        }
        return sh;
    }

    public static void main1(String[] args) {
        MySingleList mySingleList = new MySingleList();

        mySingleList.addLast(12);
        mySingleList.addLast(34);
        mySingleList.addLast(10);
        mySingleList.addLast(54);
        mySingleList.addLast(5);

        partition(mySingleList.head,20);

        mySingleList.display();


    }
}
